Integrated circuits for devices such as field programmable gate arrays comprise of logic and other functional cells that can be interconnected with each other and to the inputs (targets) and outputs (drivers) allowing for the transmission of signals within the integrated circuit. Interconnect resources or interconnects can be wires or other channels designed for carrying signals. They can also be multiplexers. A multiplexer is a switch that allows one to choose among a variety of detailed point to point signal routing paths, much like a tracked switch on a section of a railroad. Multiplexers are typically connected to the logic and functional cells and other multiplexers by other interconnects such as wires and vias.
Each driver in an integrated circuit can be designed to be connected to a set of one or more targets via logic or functional cells to form a signal net in order to implement a specific logic or function. Signal routing, or global routing, is the patterning or programming of interconnects of integrated circuits to connect each driver of an integrated circuit with its particular set of targets to form a signal net for each driver.
Traditionally, interconnect architectures for routing, also referred to herein as Interconnect Routing Architectures (IRAs), are the structures of the interconnect system for routing on an integrated circuit. They are often in the form of a mesh. “Flexibility of Interconnection Structures for Field Programmable Gate Arrays”, J. Rose and S. Brown, IEEE Journal of Solid-State Circuits. vol. 26, no. 3, Mar. 1991. Hierarchical interconnect architectures for routing, also referred to herein as Hierarchical Interconnect Routing Architectures (HIRAs), are interconnect structures for routing where the interconnect resources for routing, i.e., routing resources, can be mapped into a graph theoretic tree, also referred to herein as a tree. United States patent application, Hierarchical Multiplexer-Based Integrated Circuit Interconnect Architecture for Scalability and Automatic Generation,” having a U.S. Pat. No. 6,801,052 B2, is a HIRA where the routing resources and the core cells are placed hierarchically in a plurality of levels in the form of a tree. HIRAs provide predictable routing delay between adjacent levels of the hierarchy, have high scalability, and allow for high resource utilization.
Existing methods for the global routing of ERAs convert the routing resources to a graph consisting of a finite set of nodes together with a finite set of edges, each of which connects a pair of nodes. The classic expansion or “maze” routing methods are routing methods with algorithms that expand outwards from a driver to explore and locate all possible paths or routings to its set of targets, similar to the exploration of all possible paths in a maze. However, the complexity of these routing methods are non-polynomial (NP) hard, i.e., the work needed to find an optimal solutions increase exponentially with the number of nodes and edges in the graph. As a consequence, approximate solution methods have to be used. These methods tend to lead to suboptimal routing resource usage, either due to excess wire lengths required to route or the unnecessary branching of the routes.
Another method for routing in an IRA involves the solving of a Minimal Spanning Tree (MST) Problem for each net, i.e., for each driver and its targets. From the standpoint of resource usage, this method is attractive as it is often superior to the simple maze expansion methods as its run-time is merely polynomial. However, this method still leads to suboptimal resource usage. In IRAs that can only be mapped to a graph and not to a tree, the solving of a straight forward Minimal Spanning Tree problem does not account for that fact that most IRAs allow for branch nodes. Optimal routing for any signal net is only achieved by the optimal placement of these branch nodes. In the worse case scenario, this process is NP complete, i.e., it may require an exponential run-time. Moreover, where there are multiple nets competing for a common set of routing resources, routing congestion, i.e., the lack of sufficient routing resources that can be assigned, is often encountered, especially with routing methods where routing resource usage are suboptimal.
More advanced routing methods typically involve solving, either exactly or approximately, a Graph Steiner Minimal Tree problem. These problems are NP-hard. A provable optimal solution requires exponentially large computational time to find. Therefore, finding optimal solutions becomes intractable, except for all but very small IRAs. Approximate solutions that can be found in polynomial time are non-optimal.
As a result of routing resource constraints related to the size and power consumption of an integrated circuit, the general problem of signal routing is NP “hard” or NP complete, i.e., non-deterministic polynomial complete. The difficulty of finding a globally optimal solution can increase exponentially with the size of the routing problem, a function of the size of the IRA and the number of signal nets and the quantity of available routing resources. “New Performance-Driven FPGA Routing Algorithms”, M. J. Alexander and G. Robins, http://www.cs.virginia.edu/˜robins/FPGA/DAC 95 Paier.html.
Due to the limitations of the prior art, it is therefore desirable to have novel methods for routing with run-time that is polynomial and not NP hard and where routing resource usage is optimal.